package primary.code06_graph;

import java.util.*;

/**
 * @author Yudi Wang
 * @date 2021/7/16 11:25
 * <p>
 * 图的宽度优先遍历（不同于树，图可能存在环）
 */
public class Code02_BFS {
    //宽度优先遍历
    private static void bsf(Node node) {
        if (node == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        //存储已经遍历使用过的节点
        HashSet<Node> used = new HashSet<>();
        Node cur = node;
        queue.add(cur);
        used.add(cur);
        while (!queue.isEmpty()) {
            cur = queue.poll();
            System.out.print("  " + cur.val);
            for (Node nextNode : cur.next) {
                //判断是否已遍历到
                if (!used.contains(nextNode)) {
                    queue.add(nextNode);
                    //在加入队列后，维护 used
                    used.add(nextNode);
                }
            }
        }
    }

    private static void bsfTest(Node node) {
        if (node == null) return;
        Queue<Node> queue = new LinkedList<>();
        Set<Node> visited = new HashSet<>();
        queue.offer(node);
        visited.add(node); // 进队列即认为是访问
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            System.out.print("  " + cur.val);
            for (Node next : cur.next) {
                if (!visited.contains(next)) {
                    queue.offer(next);
                    visited.add(next);
                }
            }
        }
    }

    public static void main(String[] args) {
        //转换为自己熟悉的数据结构
        //第一个元素代表权值，第二个元素代表一条边的出边节点，第三个元素代表一条边的入边节点
        int[][] arr = {
                {4, 1, 2},
                {2, 1, 3},
                {3, 2, 3},
                {1, 3, 1},
                {1, 3, 4}};
        Graph g = GraphUtils.transferGraph(arr);
        //宽度优先遍历
        bsf(g.nodes.get(1));
        System.out.println();
        System.out.println("=======");
        bsfTest(g.nodes.get(1));
    }
}
